Lossless compression provides for significant reductions in the size of executable instructions stored in memory, also known as executable image files. Lossless compression techniques typically utilize an associative table which contains repeating bit patterns found in the file to be compressed, and which is accessed by bit patterns which reference the associative table. In this method, a file is compressed by analyzing for repeating binary patterns, and those patterns are added to a dictionary, and then the dictionary is referenced by those patterns by the index offset. The bit patterns stored are typically of variable length, and may be stored as a tree with references to the nodes and subnodes of the patterns of interest. In this method, one index may represent a 16 bit value of a tree, and another table entry may represent a 256 bit value of a different tree. In this manner, repeated occurrences of the sequences found in the file may be represented by a references to the index only. One such prior art method for lossless compression is Huffman coding, where the binary file is examined for occurrences of various strings of 1s and 0s, which are expressed as a tree which can be addressed by its values. Another similar compression method is the “zip” file format using the Ziv-Lempel-Welch (ZLW) compression, one example implementation is described in U.S. Pat. No. 4,558,302.
While the compressed image may be significantly smaller than the original uncompressed file, in the prior art, a CPU executing instructions from the compressed file must first decompress the entire file, and it is not possible to decompress instructions from a random starting point in the file, as required by a branch instruction from a CPU. FIG. 1A shows executable code instructions 100 subjected to lossless compression 102 to form a compressed file 104. FIG. 1B shows the file 104 decompressed using lossless expansion 106 which decompresses the file in a symmetric manner as compression step 102, resulting in a faithful reproduction of the original file 108 matching 100. FIG. 2 shows an embedded processor 202 with flash memory storage 204 containing a compressed image, and random access memory (RAM) 206 which contains the uncompressed image. In one prior art system, the compressed image is saved in flash memory 204 and decompressed into RAM 206, where the CPU executes the uncompressed original program instructions from RAM 206. If the compression ratio is 4:1, such that the compressed image is 25% of the size of the original uncompressed file, then the disadvantage of this approach is that RAM 206 must be four times the size of flash memory 204.
One problem of decoding compressed images is that the symbol boundaries from one compressed opcode to another are of variable length, so it is not possible to access a particular part of the compressed file in a granular manner to decompress a particular instruction without starting from an initial compression entry point and decompressing the successive values to maintain synchronization with the preceding symbols and retrieve the desired symbol for decompression into the desired opcode. One prior art approach is to compress the executable code into a series of segments, each segment starting from a landing target for a branch instruction and ending before a branch instruction, such as series of fixed length segments 416 shown in FIG. 4. This decompression method maps an incoming CPU address 408 into a look-up table LUT 404, which identifies the particular segment which contains the data for this address, which is passed as a segment number 412 from the LUT 404 along with an offset value, after which the compressed segment is retrieved from flash memory 416 and sent as data 414, the segment is decompressed by decompressor 406, and the particular offset is used to identify the desired value from the series of decompressed CPU instructions, which are presented as opcode CPU data 410. The memory requirements of the prior art system of FIG. 4 are reduced over the wholesale decompression of the image into Random Access Memory (RAM) of FIG. 2, but the use of multiple segments and look-up table 404 still requires an undesired level of overhead.
Another problem of decompressing an image into memory is that it increases the execution memory requirement. Further, when a jump or branch instruction is encountered, the execution resumes at an address which is either a relative address (with relation to the current instruction), or it is an absolute address. For either the relative or absolute address target for next instruction execution, the problem remains that the compression methods of the prior art provide variable compression ratios on an instruction by instruction basis, so it is indeterminate as to what address to branch in the compressed code, since the compression of the corrected branch address into compressed code may result in different length than the uncorrected branch location, resulting in a non-converging branch address over iterations of compression attempts. Further, if an offset value is provided to compensate, the offset value itself may compress differently, resulting in a different offset value needed, which results in a non-converging solution to the offset value.
It is desired to provide an apparatus and method for decompression of executable code without the overhead of a look-up table or the use of indeterminate or non-converging offset values where branch instructions are present.